//////////////////////////////////////////////////////////////////////////
///	Copyright (Tencent) 2007 - All Rights Reserved
///	\file:	MemObjColl.h
///	Author:	robetma.
///	Date:	[2007/04/11]
///	Description:
///		Collection for CMObj*.
//////////////////////////////////////////////////////////////////////////
#pragma once
#include "Coll.h"

class CMObj;

class CMObjPtrArray
{
public:

	// Construction
	CMObjPtrArray();

	// Attributes
	INT_PTR GetSize() const;
	INT_PTR GetCount() const;
	BOOL IsEmpty() const;
	INT_PTR GetUpperBound() const;
	void SetSize(INT_PTR nNewSize, INT_PTR nGrowBy = -1);

	// Operations
	// Clean up
	void FreeExtra();
	void RemoveAll();

	// Accessing elements
	CMObj* GetAt(INT_PTR nIndex) const;
	void SetAt(INT_PTR nIndex, CMObj* newElement);

	CMObj*& ElementAt(INT_PTR nIndex);

	// Direct Access to the element data (may return NULL)
	const CMObj** GetData() const;
	CMObj** GetData();

	// Potentially growing the array
	void SetAtGrow(INT_PTR nIndex, CMObj* newElement);

	INT_PTR Add(CMObj* newElement);

	INT_PTR Append(const CMObjPtrArray& src);
	void Copy(const CMObjPtrArray& src);

	// overloaded operator helpers
	CMObj* operator[](INT_PTR nIndex) const;
	CMObj*& operator[](INT_PTR nIndex);

	// Operations that move elements around
	void InsertAt(INT_PTR nIndex, CMObj* newElement, INT_PTR nCount = 1);

	void RemoveAt(INT_PTR nIndex, INT_PTR nCount = 1);
	void InsertAt(INT_PTR nStartIndex, const CMObjPtrArray* pNewArray);

	// Implementation
protected:
	CMObj** m_pData;   // the actual array of data
	INT_PTR m_nSize;     // # of elements (upperBound - 1)
	INT_PTR m_nMaxSize;  // max allocated
	INT_PTR m_nGrowBy;   // grow amount

public:
	~CMObjPtrArray();


protected:
	// local typedefs for class templates
	typedef CMObj* BASE_TYPE;
	typedef CMObj* BASE_ARG_TYPE;
};

class CMObjPtrList
{
protected:
	struct CNode
	{
		CNode* pNext;
		CNode* pPrev;
		CMObj* data;
	};
public:

	// Construction
	/* explicit */
	CMObjPtrList(INT_PTR nBlockSize = 10);

	// Attributes (head and tail)
	// count of elements
	INT_PTR GetCount() const;
	INT_PTR GetSize() const;
	BOOL IsEmpty() const;

	// peek at head or tail
	CMObj*& GetHead();
	const CMObj* GetHead() const;
	CMObj*& GetTail();
	const CMObj* GetTail() const;

	// Operations
	// get head or tail (and remove it) - don't call on empty list!
	CMObj* RemoveHead();
	CMObj* RemoveTail();

	// add before head or after tail
	POSITION AddHead(CMObj* newElement);
	POSITION AddTail(CMObj* newElement);


	// add another list of elements before head or after tail
	void AddHead(CMObjPtrList* pNewList);
	void AddTail(CMObjPtrList* pNewList);

	// remove all elements
	void RemoveAll();

	// iteration
	POSITION GetHeadPosition() const;
	POSITION GetTailPosition() const;
	CMObj*& GetNext(POSITION& rPosition); // return *Position++
	const CMObj* GetNext(POSITION& rPosition) const; // return *Position++
	CMObj*& GetPrev(POSITION& rPosition); // return *Position--
	const CMObj* GetPrev(POSITION& rPosition) const; // return *Position--

	// getting/modifying an element at a given position
	CMObj*& GetAt(POSITION position);
	const CMObj* GetAt(POSITION position) const;
	void SetAt(POSITION pos, CMObj* newElement);

	void RemoveAt(POSITION position);

	// inserting before or after a given position
	POSITION InsertBefore(POSITION position, CMObj* newElement);
	POSITION InsertAfter(POSITION position, CMObj* newElement);


	// helper functions (note: O(n) speed)
	POSITION Find(CMObj* searchValue, POSITION startAfter = NULL) const;
	// defaults to starting at the HEAD
	// return NULL if not found
	POSITION FindIndex(INT_PTR nIndex) const;
	// get the 'nIndex'th element (may return NULL)

	// Implementation
protected:
	CNode* m_pNodeHead;
	CNode* m_pNodeTail;
	INT_PTR m_nCount;
	CNode* m_pNodeFree;
	struct CPlex* m_pBlocks;
	INT_PTR m_nBlockSize;

	CNode* NewNode(CNode*, CNode*);
	void FreeNode(CNode*);

public:
	~CMObjPtrList();

	// local typedefs for class templates
	typedef CMObj* BASE_TYPE;
	typedef CMObj* BASE_ARG_TYPE;
};

class CMapWordToMObjPtr
{
protected:
	// Association
	struct CAssoc
	{
		CAssoc* pNext;
		CMObj* value;
		WORD key;
	};

public:

	// Construction
	/* explicit */
	CMapWordToMObjPtr(INT_PTR nBlockSize = 10);

	// Attributes
	// number of elements
	INT_PTR GetCount() const;
	INT_PTR GetSize() const;
	BOOL IsEmpty() const;

	// Lookup
	BOOL Lookup(WORD key, CMObj*& rValue) const;

	// Operations
	// Lookup and add if not there
	CMObj*& operator[](WORD key);

	// add a new (key, value) pair
	void SetAt(WORD key, CMObj* newValue);

	// removing existing (key, ?) pair
	BOOL RemoveKey(WORD key);
	void RemoveAll();

	// iterating all (key, value) pairs
	POSITION GetStartPosition() const;
	void GetNextAssoc(POSITION& rNextPosition, WORD& rKey, CMObj*& rValue) const;

	// advanced features for derived classes
	UINT GetHashTableSize() const;
	void InitHashTable(UINT hashSize, BOOL bAllocNow = TRUE);

	// Overridables: special non-virtual (see map implementation for details)
	// Routine used to user-provided hash keys
	UINT HashKey(WORD key) const;

	// Implementation
protected:
	CAssoc** m_pHashTable;
	UINT m_nHashTableSize;
	INT_PTR m_nCount;
	CAssoc* m_pFreeList;
	struct CPlex* m_pBlocks;
	INT_PTR m_nBlockSize;

	CAssoc* NewAssoc();
	void FreeAssoc(CAssoc*);
	CAssoc* GetAssocAt(WORD, UINT&, UINT&) const;

public:
	~CMapWordToMObjPtr();


protected:
	// local typedefs for CTypedPtrMap class template
	typedef WORD BASE_KEY;
	typedef WORD BASE_ARG_KEY;
	typedef CMObj* BASE_VALUE;
	typedef CMObj* BASE_ARG_VALUE;
};
